package _02array;

public class _05SearchSortArray {

    public static void main(String[] args) {
        int[] arr = new int[] {1, 4, 7, 10, 15, 19, 22, 30, 31};

        // search 10
        int maxIndex = arr.length - 1;
        int target = 10;
        int index = binarySearch(arr, 0, maxIndex, target);

        System.out.println("index: " + index);
    }

    // binary search
    // time complexity: O(log(n))
    // space complexity: O(1)
    private static int binarySearch(int arr[], int l, int r, int target) {
        while(l <= r) {
            int mid = l + (r - l) / 2;
            // arr[mid] 等于 target
            if(arr[mid] ==  target)
                return mid;
            else if(arr[mid] > target)  // target在左边
                r = mid - 1;
            else
                l = mid + 1;   // target在右边
        }
        return -1;
    }
}
